﻿using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;
using System.Text;
using VersionComparer.Comparer;

namespace VersionComparer.DataModel
{

    /// <summary>
    /// Auxiliary class for Matching functions
    /// </summary>
    public static class Match
    {
        /// <summary>
        /// Value representing a certain match
        /// </summary>
        public static double CertainMatch
        {
            get
            {
                return 1;
            }
        }
        /// <summary>
        /// Value representing a no match
        /// </summary>
        public static double NoMatch
        {
            get
            {
                return 0;
            }
        }
        /// <summary>
        /// Value representing a near certain match
        /// </summary>
        public static double NearCertainMatch
        {
            get
            {
                return 0.9999;
            }
        }
        /// <summary>
        /// String comparison for heuristics
        /// </summary>
        /// <param name="algorithm">comparison algorithm to use</param>
        /// <param name="str1">string 1 for comparison</param>
        /// <param name="str2">string 2 for comparison</param>
        /// <param name="allowCertainMatch">if true certain matches are returned when string are equal, otherwise near certain matches are returned</param>
        /// <returns>match heuristic</returns>
        public static double MatchStrings(ComparisonAlgorithm algorithm, string str1, string str2, bool allowCertainMatch = true)
        {
            if (str1 == null || str2 == null)
            {
                if (str1 == str2)
                    return allowCertainMatch ? CertainMatch : NearCertainMatch;
                else
                    return NoMatch;
            }
            if (str1 == str2)
                return allowCertainMatch ? CertainMatch : NearCertainMatch;

            int len1 = str1.Length;
            int len2 = str2.Length;

            int max = len2, min = len1;
            if (len1 > len2)
            {
                max = len1;
                min = len2;
            }

            int firstDifference = 0;
            for (; firstDifference < min; firstDifference++)
                if (str1[firstDifference] != str2[firstDifference])
                    break;
            if (firstDifference == min)
            {
                if ( firstDifference == max )
                    return allowCertainMatch ? CertainMatch : NearCertainMatch ;
                else
                    return firstDifference /max;
            }
            int lastDifference = 0;
            for (int i = len1 - 1, j = len2 - 1; i > firstDifference && j > firstDifference; i--, j--)
                if (str1[i] != str2[j])
                {
                    lastDifference = len1 - i - 1;
                    break;
                }
            double match = (firstDifference + lastDifference) / (double)max;
            
            //This should be refined, or at least configurable
            int maxLengthForLevensthein = 1000000;
            if (algorithm == ComparisonAlgorithm.Auto)
            {
                if ((len1 - firstDifference - lastDifference) * (len2 - firstDifference - lastDifference) < maxLengthForLevensthein)
                    algorithm = ComparisonAlgorithm.Thorough;
                else
                    algorithm = ComparisonAlgorithm.Fast;
            }

            if (algorithm == ComparisonAlgorithm.Thorough)
            {
                str1 = str1.Substring(firstDifference, len1- firstDifference-lastDifference);
                str2 = str2.Substring(firstDifference, len2 - firstDifference - lastDifference);
                match = LevenshteinDifference(str1, str2);
                match +=  (1.0 - match )* Math.Max ( len1- firstDifference-lastDifference, len2- firstDifference-lastDifference) /(double)max ;
            }
            if (!allowCertainMatch && match == Match.CertainMatch)
                match = Match.NearCertainMatch;
            return match;
        }
        /// <summary>
        /// Calculates the levenshtein difference between two strings 
        /// </summary>
        /// <param name="str1">first string to compare</param>
        /// <param name="str2">second string to compare</param>
        /// <returns>0 if strings are totally different, 1 if they are equal, a ratio of that for intermediate values, calculated as the number of differences divided by the max number of chars in str1 and str2</returns>
        private static double LevenshteinDifference(string str1, string str2)
        {
            #region initializations

            int str1Length = str1.Length;
            int str2Length = str2.Length;
            int maxDifference = Math.Max(str1Length, str2Length);
            if (maxDifference == 0)
                return Match.CertainMatch;

            if (str1Length == 0 || str2Length == 0)
                return Match.NoMatch;

            int[,] distances = new int[str1Length + 1, str2Length + 1];
            
            for (int i = 0; i <= str1Length;  i++)
                distances[i, 0] = i;

            for (int j = 0; j <= str2Length; j++)
                distances[0, j] = j;

            #endregion initializations

            for (int i = 1, previousi=0; i <= str1Length; i++)
            {
                
                char previousch1 = str1[previousi];
                for (int j = 1, previousj = 0; j <= str2Length; j++)
                {
                    int difference = (str2[previousj] == previousch1) ? 0 : 1;

                    distances[i, j] = Math.Min(
                                                Math.Min(distances[previousi, j] + 1, distances[i, previousj] + 1),
                                                distances[previousi, previousj] + difference);
                    previousj = j;
                }
                previousi=i;
            }
            return (maxDifference - distances[str1Length, str2Length] )/ (double) maxDifference;
        }
    }
}
